package com.datastructures2.search;

/**
 * B-树 即B树
 * @author MaoLin Wang
 * @date 2020/3/313:24
 */
public class BTreeSET<Key extends Comparable<Key>,Value> {

    /**
     * 每个B树节点最大孩子数
     */
    private static final int M=4;

    private Node root;
    /**
     * B树高度
     */
    private int height;

    /**
     * 节点对数量
     */
    private int n;

    private static final class Node{
        /**
         * 孩子数量
         */
        private int m;

        private Page[]children=new Page[M];

        public Node(int m) {
            this.m = m;
        }
    }

    /**
     * 内部节点只使用key和next
     * 外部节点只使用key和value
     */
    private static class Page{
        private Comparable key;
        private final  Object value;
        private Node next;

        public Page(Comparable key, Object value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public BTreeSET() {
        root=new Node(0);
    }

    public Value get(Key key){
        if (key==null){
            return null;
        }
        return search(root,key,height);
    }

    private Value search(Node node, Key key, int height) {
        Page[]children=node.children;
        if (height==0){
            //外部节点
            for (int i = 0; i < node.m; i++) {
                if (eq(key,children[i].key)){
                    return (Value) children[i].value;
                }
            }
        }else {
            //内部节点
            for (int i = 0; i < node.m; i++) {
                if (i+1==node.m || less(key,children[i+1].key)){
                    return search(children[i].next,key,height-1);
                }
            }
        }
        return null;
    }

    public void put(Key key,Value value){
        if (key==null){
            return;
        }
        Node u=insert(root,key,value,height);
        n++;
        if (u==null){
            return;
        }

        //需要拆分
        Node t=new Node(2);
        t.children[0] = new Page(root.children[0].key, null, root);
        t.children[1] = new Page(u.children[0].key, null, u);
        root = t;
        height++;
    }

    private Node insert(Node node, Key key, Value value, int height) {
        int i;
        Page page=new Page(key,value,null);

        //外部节点
        if (height==0){
            for ( i = 0; i < node.m; i++) {
                if (less(key,node.children[i].key)){
                    break;
                }
            }
        }else {
            for ( i = 0; i < node.m; i++) {
                if ((i+1==node.m)||less(key,node.children[i+1].key)){
                    Node u = insert(node.children[i++].next, key, value, height-1);
                    if (u == null) return null;
                    page.key = u.children[0].key;
                    page.next = u;
                    break;
                }
            }
        }
        for (int j = node.m; j >i; j--)
            node.children[j] = node.children[j-1];
        node.children[i] = page;
        node.m++;
        if (node.m < M) return null;
        else         return split(node);
    }
    // split node in half
    private Node split(Node h) {
        Node t = new Node(M/2);
        h.m = M/2;
        for (int j = 0; j < M/2; j++)
            t.children[j] = h.children[M/2+j];
        return t;
    }

    private boolean less(Comparable k1, Comparable k2) {
        return k1.compareTo(k2) < 0;
    }

    private boolean eq(Comparable k1, Comparable k2) {
        return k1.compareTo(k2) == 0;
    }

    public boolean isEmpty(){
        return size()==0;
    }

    public int size() {
        return n;
    }

    public int height(){
        return height;
    }

    public static void main(String[] args) {
        BTreeSET<String, Object> set = new BTreeSET<>();
        set.put("B",1);
        set.put("C",1);
        set.put("D",1);
        set.put("E",1);
        set.put("F",1);
        set.put("H",1);
        set.put("I",1);
        set.put("J",1);
        set.put("K",1);
        set.put("M",1);
        set.put("N",1);
        set.put("O",1);
        set.put("P",1);
        set.put("Q",1);
        set.put("R",1);
        set.put("T",1);
        set.put("U",1);
        set.put("W",1);
        set.put("X",1);
        set.put("A",1);

        String s="asdvssdag";
        String t="dvssaa";
        int n=Math.min(s.length(),t.length());
        for (int i = 0; i < n; i++) {
            if (s.charAt(i)!=t.charAt(i)){
                System.out.println(i);
                break;
            }
        }
        System.out.println(n);
    }
}
